package com.xj.algorithm.leetcode;

/**
 * 删除排序链表中的重复元素
 */
public class L83_删除排序链表中的重复元素 {

    /**
     * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
     * <p>
     * 示例 1:
     * 输入: 1->1->2
     * 输出: 1->2
     * <p>
     * 示例 2:
     * 输入: 1->1->2->3->3
     * 输出: 1->2->3
     */
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(1);
        listNode.next.next = new ListNode(2);
        ListNode res1 = deleteDuplicatesOffice(listNode);
        while (res1 != null) {
            System.out.print(res1.val);
            res1 = res1.next;
            if (res1 != null) {
                System.out.print("->");
            }
        }
        System.out.println();

        ListNode listNode2 = new ListNode(1);
        listNode2.next = new ListNode(1);
        listNode2.next.next = new ListNode(2);
        listNode2.next.next.next = new ListNode(3);
        listNode2.next.next.next.next = new ListNode(3);
        ListNode res2 = deleteDuplicatesOffice(listNode2);
        while (res2 != null) {
            System.out.print(res2.val);
            res2 = res2.next;
            if (res2 != null) {
                System.out.print("->");
            }
        }
        System.out.println();

        System.out.println(deleteDuplicatesOffice(null));
    }

    //自己的解法：快慢指针
    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        int reference = head.val;
        ListNode quick = head.next;
        ListNode slow = head;
        while (quick != null) {
            if (quick.val == reference) {
                quick = quick.next;
            } else {
                reference = quick.val;
                slow.next = quick;
                slow = slow.next;
                quick = quick.next;
            }
        }
        slow.next = null;
        return head;
    }

    //官方解法：直接操作法。相邻两个节点的值比较
    public static ListNode deleteDuplicatesOffice(ListNode head) {
        ListNode current = head;
        while (current != null && current.next != null) {
            if (current.next.val == current.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return head;
    }

}
